﻿// 1006train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <deque>

using namespace std;

/*
 选取 N 个地点设置 5G 基站，编号固定为 1 到 N
 计算出能联通这些基站的最小成本是多少
 输入描述
第一行输入表示基站的个数 N，其中 0 < N <= 20
第二行输入表示具备光纤直连条件的基站对的数目 M，其中 0 < M < N * (N - 1) / 2
第三行开始连续输入 M 行数据，格式为 X Y Z P，
其中 X Y 表示基站的编号，0 < X <= N， 0 < Y <= N 且 X 不等于 Y，
Z 表示在 X Y 之间架设光纤的成本，其中 0 < Z < 100，
P 表示是否已存在光纤连接，0 表示未连接， 1 表示已连接

输出描述
如果给定条件，可以建设成功互联互通的 5G 网络，则输出最小的建设成本，
如果给定条件，无法建设成功互联互通的 5G 网络，则输出-1

输入
3
3
1 2 3 0
1 3 1 0
2 3 5 0
输出
4
只需要在 1,2 以及 2,3 基站之间铺设光纤，其成本为 3+1=4
 */
class Union
{
public:
    unordered_map<int, int>parents;

    void addNode(int node_i)
    {
        if (parents.count(node_i) == 0)
            parents[node_i] = node_i;
    }
    int findParents(int node_i)
    {
	    while (parents[node_i]!=node_i)
	    {
            node_i = parents[node_i];
	    }
        return node_i;
    }
    void unionNode(int x, int y)
    {
	    if (findParents(x)!=findParents(y))
	    {
            parents[findParents(x)] = findParents(y);
	    }
    }
    //
};

class Solution01
{
public:
    struct Node
    {
        int x, y, val, link;
        Node() = default;
        Node(int x, int y, int val, int link) :x(x), y(y), val(val), link(link) {};
    };
    Solution01(int total, vector<vector<int>>&origin_v)
    {
        //编号固定为 1 到 N
        for (int i=1; i<=total; i++)
        {
            union_.addNode(i);
        }
        edge_count = total - 1;

        vector<Node>link_v;
        for (auto&item:origin_v)
        {
            //x, y, val, link
            Node node(item[0], item[1], item[2], item[3]);
            link_v.push_back(node);
        }

        for (auto&node:link_v)
        {
            //0 表示未连接， 1 表示已连接
	        if (node.link==1)
	        {
                int root_x = union_.findParents(node.x);
                int root_y = union_.findParents(node.y);
                if (root_x!=root_y)
                {
                    union_.unionNode(node.x, node.y);
                    edge_count--;
                }
                
	        }
        }

        int cost = 0;
        sort(link_v.begin(), link_v.end(), [](Node&node_a, Node&node_b)
        {
        	return node_a.val < node_b.val;
        });

        for (auto&node:link_v)
        {
            if (node.link == 1) continue;

            int root_x = union_.findParents(node.x);
            int root_y = union_.findParents(node.y);

            if (root_x!=root_y)
            {
                union_.unionNode(node.x, node.y);
                cost += node.val;
                edge_count--;
            }
            if (edge_count == 0) break;

        }
        if (edge_count!=0)
        {
            cout << -1;
            return;
        }

        cout << cost;

	    //Solu
    }
private:
    Union union_;
    int edge_count = 0;
};


/*
 有一座保密大楼，你从0楼到达指定楼层m，必须这样的规则乘坐电梯:
 给定一个数字序列，每次根据序列中的数字n上升n层或者下降n层，
 前后两次操作的方向必须相反，规定首次的方向向上，
 自行组织序列的顺序按规定操作到达指定楼层。
 求解到达楼层的序列组合，如果不能到达楼层，给出小于该楼层的最近序列组合。

说明:
操作电梯时不限定楼层范围
必须对序列中的每个项进行操作，不能只使用一部分。
输入描述:
第一行: 期望的楼层，取值范围[1,50]; 序列总个数，取值范围[1,23]
第二行: 序列，每个值取值范围[1,50]

输出描述
能够达到楼层或者小于该楼层最近的序列

补充说明:
操作电梯时不限定楼层范围
必须对序列中的每个项进行操作，不能只使用一部分
示例1
输入:
5 3
1 2 6
输出:
6 2 1
说明:
1 2 6

6 2 1均为可行解，按先处理大值的原则结果为6 2 1

如果不能到达楼层，给出小于该楼层的最近序列组合
 */
class Solution02
{
public:
    static bool compare(vector<int>&vec_a, vector<int>&vec_b)
    {
        int v_size = vec_a.size();

        for (int i=0; i<v_size; i++)
        {
            if (vec_a[i] == vec_b[i]) continue;
            return vec_a[i] > vec_b[i];
        }
    }

    int compute(vector<int>&track_v)
    {
        int res = 0;
        int v_size = track_v.size();

        for (int i=0; i<v_size; i++)
        {
            if (i%2==0)
            {
                res += track_v[i];
            }
            else
            {
                res -= track_v[i];
            }
        }
        return res;
	    //
    }

    void backTrack(vector<int>&num_vec, vector<bool>&checked)
    {
        if (track_v.size()==num_vec.size())
        {
            int res = compute(track_v);
            if (res==target_)
            {
                is_find = true;
                result[res].push_back(track_v);
            }
            else if (res<target_)
            {
                //小于该楼层的最近序列组合
                result[res].push_back(track_v);
            }
            return;
        }

        int v_size = num_vec.size();
        for (int i=0; i<v_size; i++)
        {
            if (checked[i]) continue;
            track_v.push_back(num_vec[i]);
            checked[i] = true;
            backTrack(num_vec, checked);
            checked[i] = false;
            track_v.pop_back();
	        //for
        }

	    //
    }

    Solution02(int target, vector<int>&num_vec)
    {
        target_ = target;
        int v_size = num_vec.size();
        vector<bool>checked(v_size, false);
        backTrack(num_vec, checked);

        if (is_find)
        {
            sort(result[target_].begin(), result[target_].end(), compare);
            
            for (auto&num: result[target_][0])
            {
                cout << num << ' ';
            }
            return;
        }

        int max_num = 0;
        for (auto&map_item:result)
        {
            max_num = max(map_item.first, max_num);
        }

        sort(result[max_num].begin(), result[max_num].end(), compare);

        for (auto& num : result[max_num][0])
        {
            cout << num << ' ';
        }
        

	    //Solu
    }
private:
    bool is_find = false;
    int target_ = 0;
    vector<int>track_v;
    unordered_map<int, vector<vector<int>>>result;
};


/*
 m个员工，买了n个月饼，m <= n
每个员工至少分1个月饼，但可以分多个，
单人分到最多月饼的个数是Max1，单人分到第二多月饼个数是Max2，Max1-Max2 <= 3
单人分到第n-1多月饼个数是Max(n-1)，
单人分到第n多月饼个数是Max(n)，Max(n-1)- Max(n) <= 3，问有多少种分月饼的方法

输入
每一行输入m n，表示m个员工，n个月饼，m<=n

输出
多少种月饼分法

示例
输入
2 4
输出
2

说明
分法有2种:
4=1+3
4=2+2
注意: 1+3和3+1算一种分法

挑选出m个非递减的数，要求相邻两个数的差值不超过3，这m个数的和为n，
问一共有多少种挑选方式
 */
class Solution03
{
public:
    Solution03(int people, int total_sum)
    {
        //Max(n-1)- Max(n) <= 3
	    //dp[i][i_value][sum]
        //第i个人拥有i_value块，总和为sum方法数

        //sum取值 1,total_sum
        vector<int>sum_v(total_sum + 1);
        //最大值，前面全部1，第i个人total_sum-(people-1)
        int max_value = total_sum - (people - 1);
        vector<vector<int>>value_v(max_value + 1, sum_v);
        vector<vector<vector<int>>>dynamic_v(people + 1, value_v);
        
        //初始化第1个数
        //第1个数是整个序列最小的数，上限total_sum/people
        for (int i_value=1; i_value<=total_sum/people; i_value++)
        {
            dynamic_v[1][i_value][i_value] = 1;
        }

        for (int i=1; i<=people-1; i++)
        {
            for (int i_value=1; i_value<=max_value; i_value++)
            {
                for (int sum=1; sum<=total_sum; sum++)
                {
                    //Max(n-1)- Max(n) <= 3
                    for (int d=0; d<=3; d++)
                    {
                        int prev = dynamic_v[i][i_value][sum];
                        int new_val = i_value + d;

                        if (new_val<=max_value && sum+new_val<=total_sum)
                        {
                            dynamic_v[i + 1][new_val][sum + new_val] += prev;

                        }

                        //for d
                    }


                    //for sum
                }
                //for i_value
            }

	        //for i
        }


        int result = 0;
        for (int i_value=1; i_value<=max_value; i_value++)
        {
            result += dynamic_v[people][i_value][total_sum];
        }
        cout << result;
        //solu
    }
};


/*
两个回合跳到最后一格
返回索引和最小的满足要求的步数组合(顺序保持steps中原有顺序)
第一行输入为每回合可能连续跳的步数，它是整数数组类型。
第二行输入为房子总格数count，它是int整数类型。
输入
[1,4,5,2]
7
输出
[5,2]
 */
class Solution04
{
public:
    Solution04(vector<int>&num_vec, int target)
    {
        unordered_map<int, int>num_map;
        int v_size = num_vec.size();
        int index_sum = INT_MAX;
        vector<int>result;
        for (int i = 0; i < v_size; i++)
        {
            int curr = num_vec[i];
            if (num_map.count(curr) > 0)
            {
                int prev_i = num_map.at(curr);
                if (prev_i + i < index_sum)
                {
                    result.clear();
                    result.push_back(target - curr);
                    result.push_back(curr);
                    index_sum = prev_i + i;
                }
            }
            else
            {
                num_map[target - curr] = i;
            }

            //for---
        }

        cout << '[';
        cout << result[0] << ',' << result[1];
        cout << ']';

	    //solu
    }
};


/*
三个回合跳到最后一格？
如果有，请输出索引和最小的步数组合，数据保证索引和最小的步数组合是唯一的。

输入
第一行输入为房子总格数count，它是整数类型int。
第二行输入为每回合可能连续跳过的步数，它是整数数组类型
输出
返回索引和最小满足要求的步数组合。
注意：顺序保持steps中的原有顺序。

1,5,2,0,2,4
9
输出
5,2,2
 */
class Solution05
{
public:
    struct Node
    {
        int val, index;
        Node() = default;
        Node(int val, int index) :val(val), index(index) {};
    };
    Solution05(vector<int>&num_vec, int target)
    {
        int v_size = num_vec.size();

        vector<Node>node_v(v_size);
        for (int i=0; i<v_size; i++)
        {
            node_v[i] = Node(num_vec[i], i);
        }
        sort(node_v.begin(), node_v.end(), [](Node& a, Node& b)
            {
				if (a.val==b.val)
				{
                    return a.index < b.index;
				}
                return a.val < b.val;
            });

        int index_sum = INT_MAX;
        vector<Node>result;

        for (int i=0; i<v_size; i++)
        {
            Node curr = node_v[i];
            int curr_t = target - curr.val;
            int curr_i = node_v[i].index;
            int left = i + 1, right = v_size - 1;

            while (left<right)
            {
                int left_val = node_v[left].val;
                int right_val = node_v[right].val;
                int left_i = node_v[left].index;
                int right_i = node_v[right].index;
                if (left_val + right_val ==curr_t)
                {
                    if (curr_i + left_i + right_i <index_sum)
                    {
                        result = { curr,node_v[left],node_v[right] };
                        index_sum = curr_i + left_i + right_i;
                    }
                    right--;
	                //
                }
                else if (left_val+right_val<curr_t)
                {
                    left++;
                }
                else if (left_val + right_val > curr_t)
                {
                    right--;
                }

            }

	        //for---
        }

        sort(result.begin(), result.end(), [](Node& a, Node& b)
            {
                return a.index < b.index;
            });

        int result_size = result.size();
        for (int i=0; i<result_size; i++)
        {
            cout << result[i].val;
            if (i!=result_size-1)
            {
                cout << ',';
            }
        }

	    //solu
    }
};


int main()
{
	{
        string input;
        getline(cin, input);
        vector<int>num_vec;
        stringstream oh_sstream(input);
        string token;

        while (getline(oh_sstream, token, ','))
        {
            num_vec.push_back(stoi(token));
        }

        string target_num;
        getline(cin, target_num);
        int target = stoi(target_num);

        Solution05 solu(num_vec, target);


        return 0;
	}
	{
        string input;
        getline(cin, input);
        vector<int>num_vec;
        int input_size = input.size();
        input = input.substr(1, input_size - 2);
        stringstream oh_sstream(input);
        string token;

        while (getline(oh_sstream, token, ','))
        {
            num_vec.push_back(stoi(token));
        }

        string target_num;
        getline(cin, target_num);
        int target = stoi(target_num);

        Solution04 solu(num_vec, target);
        return 0;
	}
	{
        int people = 2, total_sum = 4;
        //int people, total_sum;
        //cin >> people >> total_sum;
        Solution03 solu(people, total_sum);

        return 0;
	}
	{
        int target, v_size;
        cin >> target >> v_size;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }
        Solution02 solu(target, num_vec);

        return 0;
	}
    int total;
    cin >> total;

    int v_size;
    cin >> v_size;
    vector<vector<int>>link_v(v_size, vector<int>(4));
    for (int i=0; i<v_size; i++)
    {
        cin >> link_v[i][0] >> link_v[i][1] >> link_v[i][2] >> link_v[i][3];
    }
    Solution01 solu(total, link_v);
    return 0;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
